package leetcode.weekly.week335;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

//Solution3Test
public class Solution3 {

	public int findValidSplit(int[] nums) {
		int[] cnts = new int[1000001];
		boolean[] show = new boolean[1000001];
		for (int num : nums) {
			for (int j = 2; j * j <= num; j++) { // 关键点是这个尝试的边界：j * j = num
				while (num % j == 0 && num > 1) {
					num /= j;
					cnts[j]++;
				}
			}
			cnts[num]++;// 靓点
		}
		int same = 0;// 靓点
		for (int i = 0; i < nums.length - 1; i++) {
			int num = nums[i];
			for (int j = 2; j * j <= num; j++) {
				while (num % j == 0 && num > 1) {
					num /= j;
					if (!show[j]) {
						show[j] = true;
						same++;
					}
					if (--cnts[j] == 0) {
						same--;
					}
				}
			}
			if (!show[num]) {
				show[num] = true;
				same++;
			}
			if (--cnts[num] == 0) {
				same--;
			}
			if (same == 0)
				return i;
		}
		return -1;
	}

}
